A cryptographic system is a computer system that uses cryptography, typically to secure or authenticate data communication between a pair of computing devices connected to one another through a data communication link in the system. Each computing device has a cryptographic unit with the processing capacity to implement one or more cryptographic algorithms used to secure or authenticate the data communication. The cryptographic algorithms typically perform arithmetic operations on the bit strings representing parameters, messages, or data in the protocols to produce a bit string representing the output from the protocol.
Cryptographic systems may be subject to a variety of attacks by an interloper who wishes to obtain secret information. Some of these attacks are based on the physical implementation of a cryptographic system rather than a theoretical weakness in the cryptographic algorithm itself. For example, in side-channel attacks, timing information, electromagnetic emissions, power usage, or other side-channel information is used to try and determine a secret value utilized by the cryptographic unit during calculations.
Fault injection techniques may also be used by an interloper to try and determine secret information. In an attack of this nature, the interloper introduces errors into the data or arithmetic operations performed by the cryptographic unit by some means in hope that the erroneous results might reveal secret information or cause the device to perform incorrectly or not as designed. For example, an interloper may apply attacking stimuli such as incorrect clocking, incorrect power supply, or external energy sources (e.g. pulsed lasers or electromagnetic fields), and then monitor the output of the result and/or of the side-channels in the hopes of obtaining information that can be used to determine secret information.
One of the basic arithmetic operations performed in many types of cryptographic systems is a k-fold group operation referred to as exponentiation. Exponentiation is used in an RSA based cryptographic system to encrypt and decrypt messages and to sign and verify messages. The Chinese Remainder Theorem (CRT) is a basic algorithm used to perform exponentiation, and it is well known that this algorithm can be particularly vulnerable to attacks such as those described above.
In a typical RSA based cryptographic system, a correspondent A, which forms part of the cryptographic system, uses its cryptographic unit to sign messages that are verified by a correspondent B in the cryptographic system. The RSA parameters for such a scheme are represented as bit strings and typically consist of the values n=pq, d, and e, where:
p and q are secret prime numbers generated by correspondent A;
e is a positive integer chosen such that gcd(e, φ)=1, where φ=(p−1)(q−1); and
d is a number used as a private key and is selected such that ed≡1 (mod φ).
Correspondent A uses private key d for signing a message m, and (n, e) is the corresponding public information used by correspondent B to validate the signature. Correspondent A may then create a signature s by calculating s=md mod n. The recipient, correspondent B, may then verify the signature by computing se mod n and checking that this computed value corresponds to a message in the message space.
As is well known in the art, the CRT may be used by correspondent A to calculate the signature s more efficiently. In the context of an RSA system, the CRT states that given a value a1 calculated by a mod p operation, and given a value a2 calculated by a mod q operation, there exists a unique solution x modulo n=pq such that x≡a1 (mod p) and x≡a2 (mod q). A well-known method for solving x is to use Garner's algorithm, which is described in “Handbook of Applied Cryptography,” Menezes et al., CRC Press, 1997, pp. 612-613, incorporated herein by reference.
To calculate s=md mod n by employing the CRT, correspondent A first calculates signature components sp=md mod p and sq=md mod q, and then combines these values to yield s using Garner's algorithm. By applying Garner's algorithm, the resulting combination may be calculated in the computational unit of correspondent A according to the following formula:s=CRT(sp,sq)=sq+[(sp−sq)(q−1 mod p)mod p]q(mod n)  (1)
Additionally, it is a well-known mathematical fact that md mod p=mpdp mod p where mp=m mod p and dp=d mod(p−1), and similarly md mod q=mqdq mod q where mq=m mod q and dq=d mod(q−1). Therefore, when computing RSA signatures using the CRT, correspondent A need not store private key d, but instead may store values p, q, dp, dq, and q−1 mod p. In this case, when signing a message m, correspondent A uses its cryptographic unit to perform the RSA-CRT computation on the bit strings representing the message m and the RSA parameters. Specifically, the cryptographic unit first calculates message components mp and mq; next signature components sp=mpdp mod p and sq=mqdq mod q are calculated; and finally the CRT is used to derive signature s via Garner's algorithm (1) above.
As described in detail in U.S. Pat. No. 7,177,423 to Antipa (“Antipa”), incorporated herein by reference, when computing sp, or sq, correspondent A may be subject to a timing attack by an interloper wishing to determine the secret value p or q and therefore break the system. Therefore, when computing an exponentiation such as sp=md mod p or sq=md mod q, it is preferable to apply blinding, i.e., to modify the message m by a value unknown to the attacker before exponentiation and then adjust the resulting exponentiated value to retrieve the required value. A variety of blinding techniques are known in the art; however, Antipa advantageously discloses a blinding technique that avoids an inversion operation to recover the correct value after exponentiation. A summary of the blinding technique disclosed in Antipa for computing an exponentiation is as follows. Assume the cryptographic unit of correspondent A is computing the value sp=md mod p. First, the cryptographic unit generates a blinding parameter r, which is preferably randomly generated, and then performs exponentiation to calculate re mod p, where e is the RSA parameter that comprises one component of the public key. Next, the cryptographic unit combines the message m with re mod p to yield mre mod p. A small value σ is then chosen, and an intermediate value (mre)d-σ mod p is calculated, where d is the private key. This intermediate value is then multiplied by a value mσ to obtain a blinded value {tilde over (s)}p=r1−eσmd mod p. Finally, the value {tilde over (s)}pr1−eσmd mod p is unblinded by multiplying the value by reσ-1 to obtain sp=md mod p.
Conveniently, in the above protocol, the value σ can be set to be equal to 1 in order to simplify the calculations. In this case, the blinded value is reduced to {tilde over (s)}p=r(1−e)md mod p, which can be unblinded by multiplying by r(e-1) to yield sp=md mod p.
Using the Antipa blinding technique, sp and sq may be calculated in a way that inhibits p and q from being determined from side-channel attacks, such as timing attacks.
Although blinding the calculation of sp and sq, enhances protection against timing attacks by an interloper wishing to uncover p and q, it has been shown that a cryptographic system that uses the CRT to compute the value s efficiently is still vulnerable to fault injection attacks. For example, if an interloper can force one of the calculations sp or sq, say sq, to contain an error, then the signature s will be correct modulo p, but not modulo q. In this case, it has been shown that there is a significant chance that the greatest common denominator of se−m and n, is equal to secret value p, i.e. that gcd(se−m, n)=p. This may allow the interloper to determine secret information p. Such an attack is referred to as a gcd attack on an RSA-CRT implementation.
It is desired to obviate or mitigate at least one of the disadvantages described above.